{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 二叉查找树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### <该节所有代码均为本人原创>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"girk\">\n",
    "<span class=\"mark\">二叉查找树（Binary Search Tree），也称二叉搜索树和二叉排序树，是指一棵空树或者具有下列性质的二叉树：</span><br></div><i class=\"fa fa-lightbulb-o \"></i>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\bullet$ 任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；<br>\n",
    "$\\bullet$ 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；<br>\n",
    "$\\bullet$ 任意节点的左、右子树也分别为二叉查找树；<br>\n",
    "$\\bullet$ 没有键值相等的节点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " 二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合,multiset、关联数组等."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 创建搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假定任意给出一个数组，不放先假设该数组的第一个值为二叉搜索树的根结点。如　alist = [21,28,14,32,25,18,11,30,19,15] ,那么它的创建过程如下：\n",
    "\n",
    "<img src=\"image/chapter05/BST.gif\" width=450>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 不妨先定义单个结点的类\n",
    "class Node:\n",
    "    def __init__(self,root,left=None,right=None):\n",
    "        self.root = root\n",
    "        self.left = left\n",
    "        self.right = right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "      21\n",
      "  14      28\n",
      "11   18 25   32\n"
     ]
    }
   ],
   "source": [
    "def CreatTree(tree,value):\n",
    "    if value>tree.root:\n",
    "        if tree.right is None:\n",
    "            tree.right = Node(value)\n",
    "        else:\n",
    "            CreatTree(tree.right,value)\n",
    "\n",
    "    if value<tree.root:\n",
    "        if tree.left is None:\n",
    "            tree.left = Node(value)\n",
    "        else:\n",
    "            CreatTree(tree.left,value)\n",
    "\n",
    "    return tree # 一定要返回 tree\n",
    "\n",
    "# 打印前 3 层树\n",
    "def printTree(tree):\n",
    "    print('     ',tree.root)\n",
    "    print(' ',tree.left.root,'    ',tree.right.root)\n",
    "    print(tree.left.left.root,' ',\n",
    "          tree.left.right.root,tree.right.left.root,' ',tree.right.right.root)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    alist = [21,28,14,32,25,18,11,30,19,15]\n",
    "\n",
    "    for i in range(len(alist)):\n",
    "        if i == 0:                    # 首值作为树的根结点\n",
    "            tree=Node(alist[i])\n",
    "            continue\n",
    "        tree = CreatTree(tree,alist[i])  # 然后不断插入新值\n",
    "        \n",
    "    printTree(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看出，创建搜索二叉树成功！ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 插入元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "新元素的插入其实和二叉搜索树的创建过程是一样的，因此"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Insert(tree,data):\n",
    "    return CreatTree(tree,data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "27\n"
     ]
    }
   ],
   "source": [
    "tree = Insert(tree,27)\n",
    "print(tree.right.left.right.root) # 见下图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 查找元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二叉树中元素的查找也是一个递归的过程，比如在上述二叉树中查找元素27:<br>\n",
    "$\\bullet$ 根节点 21 < 27,说明27在其右子树中;<br>\n",
    "$\\bullet$ 子树结点 28 > 27,说明27在其左子树中;<br>\n",
    "$\\bullet$ 子树结点 25 < 27,说明27在其右子树中;<br>\n",
    "$\\bullet$ 子树结点　27 == 27,成功找到！\n",
    "\n",
    "\n",
    "<img src=\"image/chapter05/SearchTree.gif\" width=400>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Search(tree,data):\n",
    "    if tree.root == data:\n",
    "        return True\n",
    "    \n",
    "    elif tree.root>data:\n",
    "        if tree.left is None:return False\n",
    "        ans = Search(tree.left,data)\n",
    "    else:\n",
    "        if tree.right is None:return False\n",
    "        ans = Search(tree.right,data)\n",
    "    \n",
    "    return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由于上图中已经插入了一些新元素，因此我们先插入一些新元素，然后再执行元素查找并将它们打印出来。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "27 5 32 25 19 18 14 11 37 "
     ]
    }
   ],
   "source": [
    "new = [5,12,23,37] # 27 在 1.2 小节中已经插入\n",
    "for data in new:\n",
    "    tree = Insert(tree,data)\n",
    "\n",
    "for data in [27,5,10,32,33,26,25,19,18,14,11,22,37]:\n",
    "    if Search(tree,data):print(data,end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 中序遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"image/chapter05/SearchTree.gif\" width=300>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 11 12 14 15 18 19 21 23 25 27 28 30 32 37 "
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def Inorder(tree):\n",
    "    if tree:\n",
    "        Inorder(tree.left)\n",
    "        print(tree.root,end=' ')\n",
    "        Inorder(tree.right)\n",
    "    return True\n",
    "\n",
    "Inorder(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看到它们刚好是从小到大排序！"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 删除元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "      50\n",
      "  30      70\n",
      "20   40 60   80\n"
     ]
    }
   ],
   "source": [
    "# 创建一颗搜索二叉树,代码解释见 \"创建搜索二叉树\" 小节\n",
    "\n",
    "alist = [50,30,70,60,80,20,40]\n",
    "for i in range(len(alist)):\n",
    "    if i == 0:\n",
    "        tree = Node(alist[i])\n",
    "        continue\n",
    "    tree = CreatTree(tree,alist[i])\n",
    "\n",
    "printTree(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从二叉搜索树中删除某一元素需要先找到该元素，然后再从表中删除。一般而言，它需要考虑以下三种情况:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<__main__.Node object at 0x7fe25c684198>\n"
     ]
    }
   ],
   "source": [
    "#---------------------------- case 1 : 被删节点为叶子 -----------------------------#\n",
    "\n",
    "\"\"\"\n",
    "         50                                      50\n",
    "      /      \\              delete(20)        /      \\\n",
    "     30      70        ------------------>  30       70\n",
    "   /   \\    /   \\                            \\      /  \\ \n",
    "  20   40  60   80                           40    60  80\n",
    "  \n",
    "\"\"\"\n",
    "\n",
    "#---------------------------- case 2 : 被删节点只有一个孩子 ------------------------#\n",
    "\n",
    "\"\"\"\n",
    "     50                                        50\n",
    "  /      \\           delete(30)              /    \\\n",
    "30        70       ------------------>      40    70\n",
    "  \\      /  \\                                    /  \\ \n",
    "  40   60   80                                  60   80\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "#--------------------------- case 3 : 被删节点有两个孩子 --------------------------#\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "    50                                         60\n",
    " /      \\             delete(50)             /    \\\n",
    "40      70       ----------------->        40     70\n",
    "       /  \\                                         \\ \n",
    "      60  80                                        80\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "print(tree)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
